1. Field of Invention
This invention relates in general to error correcting systems and, in particular, to an error correcting system for correcting multibyte errors in a codeword in which the identity of the error locations and the identity of the error patterns are achieved simultaneously.
2. Cross-Referenced Application
Application Ser. No. 454,392, filed concurrently herewith, entitled "Syndrome Processing Unit for Multibyte Error Correcting Systems", A. M. Patel, assigned to the assignee of the present invention, discloses a syndrome processing unit which may be employed in the system of the present invention.
3. Description of the Prior Art
Most data storage subsystems associated with modern information handling systems employ some type of error correction system in order to obtain cost effective design for high reliability and data integrity. The ability of the data processing system to retrieve data from the storage system, i.e., access time, is a well recognized measure of the efficiency of the overall storage system. In most data processing systems, the decoding time for the error correction code is a direct factor in the total access time. As the capacity of storage devices has increased, the need for increased reliability and availability has also increased. As a result, the time required to process soft errors by the error correcting system becomes a larger percentage of the total access time. Multibyte error correcting systems suggested in the prior art require a relatively long time for decoding of the multibyte errors. This has been one of the main objections to their use in high performance storage systems.
The following references disclose basic and significant aspects of prior art error correcting systems:
1. I. S. Reed and G. Solomon, "Polynomial Codes Over Certain Finite Fields", J. Siam, 8 (1960) p. 300-304.
2. R. C. Bose and D. K. Ray-Chaudhuri, "On a Class of Error Correcting Binary Group Codes", Information and Control, 3 (1960) p. 68-79.
3. A Hocquenghem, "Codes Correcteurs d'erreurs", Chiffres (Paris) 2 (1959) p. 147-156.
4. W. W. Peterson, "Encoding and Error Correction Procedures for the Bose-Chaudhuri Codes", IEEE Transaction Information Theory, 6 (1960) p. 459-470.
5. D. C. Gorenstein and N. Zierler, "A Class of Error-Correcting Codes in p.sup.m Symbols", Journal of Soc. Indus. Applied Math. 9 (1961) p. 207-214.
6. E. R. Berlekamp, "On Decoding Binary Bose-Chaudhuri-Hocquenghem Codes", IEEE Trans. Info. Theory 11 (1965) p. 577-579.
7. J. L. Massey, "Step-by-Step Decoding of the Bose-Chaudhuri-Hocquenghem Codes", IEEE Trans. Info. Theory 11 (1965) p. 580-585.
8. R. T. Chien, "Cyclic Decoding Procedure for the Bose-Chaudhuri-Hocquenghem Codes", IEEE Trans. Info. Theory 10 (1964) p. 357-363.
9. G. D. Forney, Jr., "On Decoding BCH Codes", IEEE Trans. Info. Theory 11 (1965) p. 549-557.
10. W. W. Peterson and E. J. Weldon, Jr., Error Correcting Codes, 2nd Edition (MIT Press, 1972).
References 1, 2 and 3 provide a wide class of cyclic error correcting codes which are commonly known as Reed-Solomon Codes and BCH Codes. These codes, when defined over nonbinary or extended binary finite fields, can be used for correction of symbol errors as binary byte errors.
References 4 and 5 provide the basic key to the solution of the multi-error decoding problem by suggesting the use of the "error locator polynomial". These references (4 and 5) suggest the use of a set of linear equations to solve for the coefficients of the error locator polynomial. References 6 and 7 suggest the use of an iterative method to compute the coefficients of the error locator polynomial. The roots of the error locator polynomial represent the locations of the symbols in error.
Reference 8 suggests a simple mechanized method, the "Chien Search", for searching these roots using a cyclic trial and error procedure, while reference 9 provides further simplification in the computation of error values in the case of codes with non-binary or higher order binary symbols.
The contribution of the error locator polynomial in references 4 and 5 was significant in that the roots of this polynomial represent the locations of the symbols in error for a multibyte error correcting system. The cross-referenced copending application discloses an improved syndrome processing unit for developing the coefficients of the error locator polynomial.
The method of decoding multibyte errors in a multibyte error correcting system generally comprises four sequential steps:
Step 1--calculating of the error syndromes.
Step 2--determination of the coefficients of the error locator polynomial from the error syndromes.
Step 3--identifying the error locations from the error locator polynomial by "Chien Search".
Step 4--determination of the byte error values for each of the error locations.
All known methods for decoding multiple errors require completion of step 3 before beginning step 4. Because of that situation, prior art systems also require additional hardware to accumulate the results of step 3 for use subsequently by the hardware that implements step 4. References 6 and 10 provide good discussion on the prior art decoding methods.